#include "main/utils.h"
using namespace std;

class Solution {
  public:
    vector<int> productExceptSelf(vector<int>& nums) {
      int len = nums.size();
      vector<int> left(len);
      vector<int> right(len);
      left[0] = 1;
      right[len - 1] = 1;
      for (int i = 1; i < len; ++i) {
        left[i] = left[i - 1] * nums[i - 1];
      }
      for (int i = len - 2; i >= 0; --i) {
        right[i] = right[i + 1] * nums[i + 1];
      }
      vector<int> output;
      for (int i = 0; i < len; ++i) {
        output.push_back(left[i] * right[i]);
      }
      return output;
    }

    vector<int> productExceptSelf1(vector<int>& nums) {
      int len = nums.size();
      vector<int> output(len);
      output[0] = 1;
      for (int i = 1; i < len; ++i) {
        output[i] = output[i - 1] * nums[i - 1];
      }
      int tmp = 1;
      for (int i = len - 1; i >= 0; --i) {
        output[i] = output[i] * tmp;
        tmp *= nums[i];
      }
      return output;
    }
};

int main() {
  vector<int> input = {1, 2, 3, 4};
  Solution su;
  auto output = su.productExceptSelf(input);
  printVec("output", output);

  input = {1, 2, 3, 4};
  output = su.productExceptSelf1(input);
  printVec("output1", output);
}
